package arrays;

/**
 * 数组查询重复元素
 * 题目：
 * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，
 * 但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 *
 * 要求时间复杂度为O(N)，空间复杂度为O(1)
 *
 * @Author Gavin
 * @date 2022.08.06 14:38
 */
public class array_20 {
    public int solution(int[] nums){
        if(nums==null||nums.length<=0)return -1;
        for (int i = 0; i < nums.length; i++) {
            //如果数组的值和数组值下标对应的数组的值相等了说明就有重复的元素了
            while (nums[i]!=i){
                if(nums[nums[i]]==i)return nums[i];
                int temp=nums[nums[i]];
                nums[nums[i]]=nums[i];
                nums[i]=temp;
            }
        }
        return -1;
    }
}
